BZOJ2339【HNOI2011】卡农 <计数DP+组合数学>

Problem

【HNOI2011】卡农

Description

Input

Output

Sample

标签：计数DP

Solution

考试时没想出来，不过听了觉得挺简单的。

首先把每个片段看成一个数，每个音阶看成该数的一位，则每位为或，题意可以转化为求在中选个数使其异或和为的方案数。我们先不考虑无序性，求出所有排列后除即为答案。

设为选个数的方案数，考虑先选个数，最后一个数即为前面的数的异或和，这样才能使总异或和位。那么如果不考虑限制，直接选则有种选法。

只可能有两种不合法的情况，即最后一个数位或最后一个数在前面个数种出现过。对于第一种情况，不合法方案数为选个数的合法方案数，即为。而对于第二种情况，去掉相同的数后，其他数异或和为，这样就有中方案，而去掉的数的位置有种选法，去掉的数的值有种选法，故共会去掉种不合法方案。

于是，方程为

Code

#include <bits/stdc++.h>
#define MAX_N 1000000
#define MOD 100000007
using namespace std;
typedef long long lnt;
template <class T>
inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, m;	lnt p, q, c, f[MAX_N+5], g[MAX_N+5], inv[MAX_N+5] = {1LL, 1LL};
void init(int n) {for (int i = 2; i <= n; i++) inv[i] = (MOD-MOD/i*inv[MOD%i]%MOD)%MOD;}
int main() {
    read(m), read(n), init(n), p = f[0] = c = 1LL, f[1] = 0LL, g[1] = 1LL;
    for (int i = 1; i <= m; i++) (p *= 2) %= MOD; (p += MOD-1) %= MOD, q = p;
    for (int i = 2; i <= n; i++, (q += MOD-1) %= MOD) g[i] = g[i-1]*q%MOD;
    for (int i = 2; i <= n; i++) f[i] = (g[i]-(f[i-1]+1LL*(i-1)*(p-i+2)%MOD*f[i-2]%MOD)%MOD+MOD)%MOD;
    for (int i = 1; i <= n; i++) (c *= inv[i]) %= MOD;	return printf("%lld", f[n]*c%MOD), 0;
}